import java.util.Stack;

import static com.sun.awt.SecurityWarning.getSize;

public class MySingleList {
    static class ListNode {
        public int val;//存储数据
        public ListNode next;//存储下一个节点的位置

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//代表当前链表的头节点引用

    //生成一个单项链表
    public void createLink() {

    }

    //遍历列表
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;

        }
        System.out.println();
    }

    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;

        }
        System.out.println();
    }


    //查找关键字k 是否在单链表中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }

    //尾插法
    public void addLast(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = listNode;
    }

    //任意位置插入
    public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndexSubOne(index);
        ListNode listNode = new ListNode(data);
        listNode.next = cur.next;
        cur.next = listNode;
    }


    //index-1 步
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //判断index是否合法
    private void checkIndex(int index) throws ListIndxOutOfException {
        if (index < 0 || index > size()) {
            throw new ListIndxOutOfException("idnex 位置不合法");
        }
    }

    //删除第一个出现的key
    public void remove(int key) {
        if (head == null) {
            return;//一个节点都没有
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode cuer = searchPrev(key);
        if (cuer == null) {
            return;
        }
        ListNode del = cuer.next;
        cuer.next = del.next;

    }

    private ListNode searchPrev(int key) {

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所以的key
    public void removeAllkey(int key) {
        if (head == null) {
            return;
        }
        ListNode plev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                plev.next = cur.next;
                cur = cur.next;
            } else {
                plev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key) {
            head = head.next;
        }
    }

    //清空
    public void clear() {
        head = null;
    }

    //删除链表中等于给定值 val 的所有节点。
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode plev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == val) {
                plev.next = cur.next;
            } else {
                plev = cur;
            }
            cur = cur.next;
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    //牛客          链  表  反  转
    public ListNode ReverseList() {
        if (head == null) {
            return null;
        }
        //说明只有一个节点
        if (head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNet = cur.next;
            cur.next = head;
            head = cur;
            cur = curNet;
        }
        return head;
    }

    //给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

    //递归打印链表
    public void display3(ListNode pHead) {
        if (pHead == null) {
            return;
        }
        if (pHead.next == null) {
            System.out.print(pHead.val + " ");
            return;
        }
        display3(pHead.next);
        System.out.print(pHead.val + " ");

    }

    public void display4(ListNode pHead) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()) {
            ListNode top = stack.pop();
            System.out.print(top.val + " ");
        }
        System.out.println();
    }




}


